package class03;

import java.util.ArrayList;
import java.util.List;

/**
 * 将多茶树转为二叉树
 */
public class Code05_EncodeNaryTreeToBinaryTree {
    // 多叉树
    static class Node {
        int val;
        List<Node> children;

        Node(int val, List<Node> children) {
            this.val = val;
            this.children = children;
        }
    }
    // 二叉树

    static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;

        TreeNode(int value) {
            this.value = value;
        }
    }


    TreeNode encode(Node root) {
        if (null == root) {
            return null;
        }

        TreeNode head = new TreeNode(root.val);
        // 将多叉树的叶子节点都放到二叉树的左子树的右侧范围；当然也可以放到右子树的左侧范围
        head.left = en(root.children);
        return head;
    }

    TreeNode en(List<Node> c) {
        TreeNode head = null;
        TreeNode cur = null;

        for (Node child : c) {
            TreeNode node = new TreeNode(child.val);
            if (head == null) {
                head = node;
            } else {
                cur.right = node;
            }
            cur = node;
            cur.left = en(child.children);
        }
        return head;
    }


    Node decode(TreeNode root) {
        if (root == null) {
            return null;
        }
        return new Node(root.value, de(root.left));
    }

    List<Node> de(TreeNode node) {
        List<Node> list = new ArrayList<>();
        while (node != null) {
            Node cur = new Node(node.value, de(node.left));
            list.add(cur);
            node = node.right;
        }
        return list;
    }
}
